Masala #1146

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 28 %
14

  

Radio

Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun \(N\) ta Radio o’rnatilgan. Har bir radioning ovoz balandligi \(K\) ga teng. Radioda yangilik eshittirilganda \(A\)- koordinatada bo’lgan uyga \(B\)-koordinatada joylashtirilgan radioning ovozi \(max(K-|A-B|, 0)\) balandlikda eshitiladi. Sizga \(M\) ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.


Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida uchta butun son, \(N(1 \le N \le 250000)\), \(M(1 \le M \le 250000)\) va \(K(1 \le K \le 10^9)\) sonlari kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(B_i(1 \le i \le N, 0 \le B_i \le 10^9)\) Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, \(A_i(1 \le i \le M, 0 \le A_i \le 10^9)\) uylarning joylashgan koordinatalari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.

 


Misollar
# input.txt output.txt
1
1 5 10
20
20 15 28 10 32
10
5
2
0
0
2
3 4 100
116 194 258
57 155 222 360
41
61
72
0
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin